Sort a linked list

Time: O(NlogN); Space: O(logN) for stack call; medium

Sort a linked list in O(NLogN) time using constant space complexity.

Example 1:

Input: linked-list: 4->2->1->3

Output: 1->2->3->4

Example 2:

Input: linked-list: -1->5->3->4->0

Output: -1->0->3->4->5

[1]:

class ListNode:
    """
    Singly-linked list
    """
    def __init__(self, x):
        self.val = x
        self.next = None

    def __repr__(self):
        if self:
            return "{} -> {}".format(self.val, repr(self.next))

class Solution1(object):
    def sortList(self, head) -> ListNode:
        '''
        :type head: ListNode
        :rtype: ListNode
        '''
        if head == None or head.next == None:
            return head

        fast, slow, prev = head, head, None
        while fast != None and fast.next != None:
            prev, fast, slow = slow, fast.next.next, slow.next
        prev.next = None

        sorted_l1 = self.sortList(head)
        sorted_l2 = self.sortList(slow)

        return self.mergeTwoLists(sorted_l1, sorted_l2)

    def mergeTwoLists(self, l1, l2):
        dummy = ListNode(0)

        cur = dummy
        while l1 != None and l2 != None:
            if l1.val <= l2.val:
                cur.next, cur, l1 = l1, l1, l1.next
            else:
                cur.next, cur, l2 = l2, l2, l2.next

        if l1 != None:
            cur.next = l1
        if l2 != None:
            cur.next = l2

        return dummy.next

[3]:

s = Solution1()
head = ListNode(4)
head.next = ListNode(2)
head.next.next = ListNode(1)
head.next.next.next = ListNode(3)
print(s.sortList(head))

head = ListNode(-1)
head.next = ListNode(5)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(0)
print(s.sortList(head))

1 -> 2 -> 3 -> 4 -> None
-1 -> 0 -> 3 -> 4 -> 5 -> None